State of the art navigation devices provide users with a large amount of useful information and search options regarding routes to be traveled, Point Of Interests (POIs), in the vicinity of calculated routes or in the vicinity of a device position, names of cities, streets or buildings, traffic information and so on. Depending on the services the navigation system is going to provide, navigation devices have stored in their databases large amounts of navigation data associated with, for instance, routing, map displaying, destination entry, POIs, traffic information.
When calculating a route on basis of user inputs and stored navigation data, a routing algorithm must be able to address all possible route links in the navigation database being used for route calculation and to hold the calculated route in a main memory of the navigation device. Thus, in order to get access to particular navigation data from the large amount of stored navigation data an addressing scheme is required. In general, the used addressing scheme is closely related with the data structuring in the database.
State of the art navigation databases (for instance, navigation databases compliant with Navigation Data Standard (NDS) storage format) use a global tiling scheme for navigation data addressing. The data structure and addressing scheme according to NDS will be described with reference to FIGS. 1 and 2 in more detail.
As illustrated in FIG. 1a, NDS provides 16 data levels (cf. x-axis in FIG. 1a: the highest data level is labeled Level 0, the lowest data level is labeled Level 15) for routing data. Specific data levels are assigned to routing data representing roads of specific road functional classes (FC) (i.e., FC1 to FC4 roads in accordance with the international classification standard for roads). In this context, NDS defines Level 13 as base level comprising routing data of FC0 to FC4 roads. Level 13 thus comprises the entire road network from highways to local small roads and, therefore, the highest road network resolution. As further illustrated in FIG. 1a, the road network resolution continuously decreases with decreasing level number. For instance, data levels 10, 9, 8 and 6 are merely associated with FC0 to FC3 roads, FC0 to FC2 roads, FC0 to FC1 roads (corresponding to a road network merely consisting of highways) and FC0 roads, respectively (cf. crosses in FIG. 1a). For clarity reasons, it should be noted that not all levels supported by NDS need to be available in a database. In the embodiment shown in FIG. 1a only Levels 6, 8, 9 10, and 13 are associated with routing data.
Each NDS level has its own underlying global tiling structure. A tile represents a rectangular territorial section in the global coordinate system having a predetermined size. The tile structure for each level is derived from a global tiling scheme that will be briefly discussed by referring to FIG. 2a. For Level 0 the surface of the earth is partitioned into two tiles, one tile covering the earth surface from 0° to +180° line of longitude (tile 1 in FIG. 2) and one tile covering the earth surface from 0° to −180° line of longitude (tile 2 in FIG. 2). For the subsequent Level 1, the two tiles are each split up into four tiles (only shown for tile 2 in FIG. 2). Each tile of Level 1 is split up again into four tiles (cf. hatched area) for Level 2 and so on. This hierarchical splitting scheme is continued through all levels down to the base level. More generally, for level k, with k=0, 1, 2, . . . 15, 2(2k+1) tiles are generated. While Level 0 comprises only two tiles covering the whole surface of the earth, 227 tiles are provided for structuring base Level 13, in which each tile covers a rectangular territorial section of approximately 2.5 km×2.5 km.
The NDS sub-structuring of NDS data levels is exemplarily illustrated for NDS level 9 in FIGS. 1b and 1c. FIG. 1b shows four tiles 201, 203, 205, 207 covering a local territorial section around the city “Munich” (cf. elliptical shadowed area). Further, route links L1 to L8 represent some roads of the city road network which are organized in the corresponding navigation database (cf. navigation database comprising the geographic region Germany in FIG. 1c) as follows. Route links L2, L8 of tile 201 (cf. FIG. 1b) are stored in a tile block with tile identifier T-ID 10111, route links L3, L4 and L5 in another tile block with T-ID 10112, route link L1 in a tile block with T-ID 10113 and route links L6, L7 in tile block with T-ID 10114 (please note that NDS stores route links extending over tile boundaries in the tiles in which the route links have their starting point). Similarly, also basic map display data may be organized in accordance with the underlying tile structure.
NDS uses the global T-ID in order to address individual route links within a tile. The structure of the T-ID is closely connected with the coding of the Geographic coordinate system used in NDS and illustrated in FIGS. 2a and 2b. 
The longitude and latitude coordinates (x- and y-coordinates) are represented by 32 bit and 31 bit integers, respectively. Thus, an NDS coordinate unit corresponds to 90/230 degrees (note scaling factor 230) of longitude and latitude. The longitude and latitude integer values are further mapped to a single integer value using Morton mapping. The received Morton code represents a 63 bit integer received form a bit interleaving of the 32 bit and 31 bit integers for longitude and latitude. On the other hand, the Geographic coordinate system is partitioned for level k into 2(2k+1)) tiles. A tile number of a given tile in level k can be deduced from the most significant 2k+1 bits of the Morton code of a coordinate lying within that tile. Therefore, 2k+1 bits are required in order to unambiguously address a single tile within level k. Consequently, at least 27 bits are required for addressing Level 13 tiles.
In order to further differentiate between tiles of different levels, additional addressing bits are required. As shown in FIG. 2b, each T-ID in NDS is composed of a level number and the tile number. For a navigation database having a level and tile structure as shown in FIGS. 1a-1c a 32 bit ID is necessary for unambiguously addressing each tile of an arbitrary level. Further, NDS suggests a 16 bit route link identifier (L-ID) for addressing route links within each tile. Such a memory-consuming L-ID is necessary in order to address all possible route links within each specific tile, since NDS does not distinguish between tiles having high and low density of route links (for instance, tiles covering large cities may comprise large number of route links, whereas tiles covering mountains (e.g., Himalaya) or oceans may comprise a few route links (e.g., links representing ferry connections) or may be void). In sum, a memory-consuming 48 bit ID is required in order to address a single route link in NDS.